package class14;

import java.util.PriorityQueue;

/**
 * 一块金条切成两半，是需要花费和长度数值一样的铜板
 * 比如长度为20的金条，不管怎么切都要花费20个铜板，一群人想整分整块金条，怎么分最省铜板?
 * 例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
 * 如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板
 * 但如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板
 * 输入一个数组，返回分割的最小代价
 */
public class Code02_LessMoneySplitGold {

    // 暴力解法
    public static int lessMoney1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr, 0);
    }

    private static int process(int[] arr, int price) {
        if (arr.length == 1) {
            return price;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; ++i) {
            for (int j = i + 1; j < arr.length; ++j) {
                int[] nexts = reduce(arr, i, j);
                result = Math.min(result, process(nexts, price + arr[i] + arr[j]));
            }
        }
        return result;
    }

    private static int[] reduce(int[] arr, int i, int j) {
        int[] nexts = new int[arr.length - 1];
        int nextsIndex = 0;
        for (int x = 0; x < arr.length; ++x) {
            if (x != i && x != j) {
                nexts[nextsIndex++] = arr[x];
            }
        }
        nexts[nextsIndex] = arr[i] + arr[j];
        return nexts;
    }

    // 贪心策略解法，哈夫曼树思想求解，每次拿最小的两个数合并，即可得出最小代价
    public static int lessMoney2(int[] arr) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.add(num);
        }
        int result = 0;
        while (minHeap.size() > 1) {
            int temp = minHeap.poll() + minHeap.poll();
            result += temp;
            minHeap.add(temp);
        }
        return result;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 10000;
        int maxSize = 6;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            if (lessMoney1(arr) != lessMoney2(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}